package com.chenken;

import java.util.Comparator;

/**
  * 红黑树
 * 也是一种自平衡的二叉搜索树
 * 红黑树必须满足以下5条性质
 * 	1.节点必须是RED或者BLACK
 * 	2.根节点必须是Black
 * 	3.叶子节点(空节点)都是Black
 * 	4.RED节点的子节点都是BLACK
 * 		RED节点的父节点都是BLACK
 *             从根节点到叶子节点的所有路径上不能有连续的2个RED节点
 * 	5.从任意一个节点到叶子结点的所有路径都包含相同数目的BLACK节点
 */
public class RBTree<E> extends BBST<E>{
	
	private static final boolean RED = false;
	
	private static final boolean BLACK = true;
	
	public RBTree() {
		this(null);
	}
	
	public RBTree(Comparator<E> Comparator) {
		super(Comparator);
	}
	
	private Node<E> color(Node<E> node,boolean color) {
		if(node == null) return node;
		((RBNode<E>)node).color = color;
		return node;
	}
	
	private Node<E> red(Node<E> node){
		return color(node,RED);
	}
	
	private Node<E> black(Node<E> node){
		return color(node,BLACK);
	}
	
	private boolean colorOf(Node<E> node) {
		return node == null ? BLACK : ((RBNode<E>)node).color;
	}
	
	private boolean isBlack(Node<E> node) {
		return colorOf(node) == BLACK;
	}
	
	private boolean isRed(Node<E> node) {
		return colorOf(node) == RED;
	}
	
	@Override
	protected void afterAdd(Node<E> node) {
		Node<E> parent = node.parent;
		//	添加的是根节点 或者 上溢到达了根节点
		if(parent == null) {
			black(node);
			return;
		}
		//	如果父节点是黑色,直接返回
		if(isBlack(parent)) {
			return;
		}
		//	叔父节点
		Node<E> uncle = parent.sibling();
		//	祖父节点.先将祖父节点染红
		Node<E> grand = red(parent.parent);		
		if(isRed(uncle)) {	//	叔父节点是红色[B树节点上溢]
			black(uncle);
			black(parent);
			//	把祖父节点当做是新添加的节点
			afterAdd(grand);
			return;
		}
		//	叔父节点不是红色
		if(parent.isLeftChild()) {//L
			if(node.isLeftChild()) {//LL
				black(parent);
			}else {	//LR
				black(node);
				rotateLeft(parent);
			}
			rotateRight(grand);
		} else { // R
			if (node.isLeftChild()) { // RL
				black(node);
				rotateRight(parent);
			} else { 	// RR
				black(parent);
			}
			rotateLeft(grand);
		}
	}

	/**
	 * 1.如果删除的是红色，不用做任何处理
	 * 2.如果删除的是黑色
	 * 		2.1如果有红色的替代子节点，将替代子节点染成黑色即可
	 * 			
	 * 		2.2如果没有替代子节点，是黑色叶子结点
	 * 			sibling是黑色，sibling至少有一个RED子节点
	 * 				表示sibling能借一个元素，进行旋转操作
	 * 				旋转之后的中心节点继承parent的颜色
	 * 				旋转之后的左右节点染成BLACK
	 * 			sibling是黑色，sibling没有RED子节点
	 * 				父节点下溢，将sibling染成RED，parent染成BLACK
	 * 
	 * 			sibling是红色
	 * 				sibling染成BLACK，parent染成RED，进行旋转
	 * 		
	 * 				
	 */
	@Override
	protected void afterRemove(Node<E> node,Node<E> replacement) {
		//	删除的是红色节点
		if(isRed(node)) {
			return;
		}
		//	用以取代node的子节点是红色
		if(isRed(replacement)) {
			black(replacement);
			return;
		}
		//	删除的是黑色叶子节点
		Node<E> parent = node.parent;
		//1.删除的是根节点
		if(root == node) {
			return;
		}
	}

	@Override
	protected Node<E> createNewNode(E element,Node<E> parent) {
		return new RBNode<E>(element, parent);
	}
	
	private static class RBNode<E> extends Node<E>{
		
		boolean color = RED;
		
		public RBNode(E element, Node<E> parent) {
			super(element, parent);
		}

		@Override
		public String toString() {
			String str = "";
			if(color == RED) {
				str = "RED_";
			}else {
				str = "BLACK_";
			}
			return str+element.toString();
		}
	}

}
